"""
解题思路

这道题目的难点有其二，一来是如何确认每个最小值的区间，一个是如何计算每个最小值对应多少的数组。

首先的难点是，如何理解这道题目？我的设想是，数组中每个元素都会作为一个区间的最小值，这样我们就可以获得一个数组区间，
我们利用数组区间中的范围就可以算出一个区间内包含多少子区间，包含的子区间乘上当前值最后便是答案。

所以问题1：如何获得区间？简单来说，区间就是以当前值为最小值的范围有多大。假设我们栈可以做单调递增，则当前元素
的左区间应当是栈顶元素的下一个位置；而右区间应当是下一个比当前值更小的元素的位置。故我们可以通过栈的方式调用，这与739题目相似。
这样我们就可以获得一个区间列表。

问题2，如何根据区间列表计算有多少区间呢？
假设数组(3, 2, 1, 4)，数组1前有两个元素，后面有1个元素，其最终和1匹配的个数应当是6个。如何计算呢？
即前面元素(3, 2, 1)有3中组合(1),(2,1),(3,2,1)，后面元素有(1),(1,4)两种；两两组合之下就有了6中情况。
故将问题1和问题2的思路组合起来就可以得到最后结果

"""



class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        arr.append(-1)
        ans, stack = 0, [-1]
        for r, x in enumerate(arr):
            while len(stack) > 1 and arr[stack[-1]] >= x:
                i = stack.pop()
                ans += arr[i] * (i - stack[-1]) * (r - i)
            stack.append(r)
        return ans % (10 ** 9 + 7)